home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / system / filesyst / dosfs / dosfsck_.z / dosfsck_ / dosfsck / fat.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-11  |  7.6 KB  |  279 lines
  1. /* fat.c  -  Read/write access to the FAT */
  2.  
  3. /* Written 1993 by Werner Almesberger */
  4.  
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include <unistd.h>
  10.  
  11. #include <linux/msdos_fs.h>
  12.  
  13. #include "common.h"
  14. #include "dosfsck.h"
  15. #include "io.h"
  16. #include "fat.h"
  17.  
  18.  
  19. static void get_fat(FAT_ENTRY *entry,void *fat,int cluster,int fat16)
  20. {
  21.     unsigned char *ptr;
  22.  
  23.     if (fat16) entry->value = CF_LE_W(((unsigned short *) fat)[cluster]);
  24.     else {
  25.     ptr = &((unsigned char *) fat)[cluster*3/2];
  26.     entry->value = 0xfff & (cluster & 1 ? (ptr[0] >> 4) | (ptr[1] << 4) :
  27.       (ptr[0] | ptr[1] << 8));
  28.     }
  29.     entry->owner = NULL;
  30. }
  31.  
  32.  
  33. void read_fat(DOS_FS *fs)
  34. {
  35.     int fat16,eff_size,i;
  36.     void *first,*second,*use;
  37.     int first_ok,second_ok;
  38.  
  39.     fat16 = fs->clusters > MSDOS_FAT12;
  40.     eff_size = fat16 ? (fs->clusters+2)*2 : ((fs->clusters+2)*3+1)/2;
  41.     first = alloc(eff_size);
  42.     second = alloc(eff_size);
  43.     fs_read(fs->fat_start,eff_size,first);
  44.     fs_read(fs->fat_start+fs->fat_size,eff_size,second);
  45.     if (!memcmp(first,second,eff_size)) use = first;
  46.     else {
  47.     first_ok = CF_LE_W(*(unsigned short *) first) == (fat16 ? 0xfff8 :
  48.       0xff8);
  49.     second_ok = CF_LE_W(*(unsigned short *) second) == (fat16 ? 0xfff8 :
  50.       0xff8);
  51.     if (first_ok && !second_ok) {
  52.         printf("FATs differ - using first FAT.\n");
  53.         fs_write(fs->fat_start+fs->fat_size,eff_size,use = first);
  54.     }
  55.     if (!first_ok && second_ok) {
  56.         printf("FATs differ - using second FAT.\n");
  57.         fs_write(fs->fat_start,eff_size,use = second);
  58.     }
  59.     if (first_ok && second_ok)
  60.         if (interactive) {
  61.         printf("FATs differ but appear to be intact. Use which FAT ?\n"
  62.           "1) Use first FAT\n2) Use second FAT\n");
  63.         if (get_key("12","?") == '1')
  64.             fs_write(fs->fat_start+fs->fat_size,eff_size,use = first);
  65.         else fs_write(fs->fat_start,eff_size,use = second);
  66.         }
  67.         else {
  68.         printf("FATs differ but appear to be intact. Using first "
  69.           "FAT.\n");
  70.         fs_write(fs->fat_start+fs->fat_size,eff_size,use = first);
  71.         }
  72.     if (!first_ok && !second_ok) {
  73.         printf("Both FATs appear to be corrupt. Giving up.\n");
  74.         exit(1);
  75.     }
  76.     }
  77.     fs->fat = qalloc(&mem_queue,sizeof(FAT_ENTRY)*(fs->clusters+2));
  78.     for (i = 2; i < fs->clusters+2; i++) get_fat(&fs->fat[i],use,i,fat16);
  79.     for (i = 2; i < fs->clusters+2; i++)
  80.     if (fs->fat[i].value >= fs->clusters+2 && (fs->fat[i].value < (fat16 ?
  81.       0xfff7 : 0xff7))) {
  82.         printf("Cluster %d out of range (%d > %d). Setting to EOF.\n",i-2,
  83.           fs->fat[i].value,fs->clusters+2-1);
  84.         set_fat(fs,i,-1);
  85.     }
  86.     free(first);
  87.     free(second);
  88. }
  89.  
  90.  
  91. void set_fat(DOS_FS *fs,int cluster,int new)
  92. {
  93.     unsigned char data[2];
  94.     int fat16,offs;
  95.  
  96.     fat16 = fs->clusters > MSDOS_FAT12;
  97.     if (new < 0) new += fat16 ? 0xfff9 : 0xff9;
  98.     fs->fat[cluster].value = new;
  99.     if (fat16) {
  100.     offs = fs->fat_start+cluster*2;
  101.     *(unsigned short *) data = CT_LE_W(new);
  102.     }
  103.     else {
  104.     offs = fs->fat_start+cluster*3/2;
  105.     if (cluster & 1) {
  106.         data[0] = ((new & 0xf) << 4) | (fs->fat[cluster-1].value >> 8);
  107.         data[1] = new >> 4;
  108.     }
  109.     else {
  110.         data[0] = new & 0xff;
  111.         data[1] = (new >> 8) | (cluster == fs->clusters-1 ? 0 :
  112.           (0xff & fs->fat[cluster+1].value) << 4);
  113.     }
  114.     }
  115.     fs_write(offs,2,&data);
  116.     fs_write(offs+fs->fat_size,2,&data);
  117. }
  118.  
  119.  
  120. int bad_cluster(DOS_FS *fs,int cluster)
  121. {
  122.     return fs->fat[cluster].value == (fs->clusters > MSDOS_FAT12 ? 0xfff7 :
  123.       0xff7);
  124. }
  125.  
  126.  
  127. int next_cluster(DOS_FS *fs,int cluster)
  128. {
  129.     unsigned short value,limit;
  130.  
  131.     value = fs->fat[cluster].value;
  132.     limit = fs->clusters > MSDOS_FAT12 ? 0xfff7 : 0xff7;
  133.     if (value == limit)
  134.     die("Internal error: next_cluster on bad cluster");
  135.     return value < limit ? value : -1;
  136. }
  137.  
  138.  
  139. unsigned int cluster_start(DOS_FS *fs,int cluster)
  140. {
  141.     return fs->data_start+(cluster-2)*fs->cluster_size;
  142. }
  143.  
  144.  
  145. void set_owner(DOS_FS *fs,int cluster,DOS_FILE *owner)
  146. {
  147.     if (owner && fs->fat[cluster].owner)
  148.     die("Internal error: attempt to change file owner");
  149.     fs->fat[cluster].owner = owner;
  150. }
  151.  
  152.  
  153. DOS_FILE *get_owner(DOS_FS *fs,int cluster)
  154. {
  155.     return fs->fat[cluster].owner;
  156. }
  157.  
  158.  
  159. void fix_bad(DOS_FS *fs)
  160. {
  161.     int limit,i;
  162.  
  163.     limit = fs->clusters > MSDOS_FAT12 ? 0xfff7 : 0xff7;
  164.     for (i = 2; i < fs->clusters+2; i++)
  165.     if (!get_owner(fs,i) && fs->fat[i].value != limit)
  166.         if (!fs_test(cluster_start(fs,i),fs->cluster_size)) {
  167.         printf("Cluster %d is unreadable.\n",i);
  168.         set_fat(fs,i,-2);
  169.         }
  170. }
  171.  
  172.  
  173. void reclaim_free(DOS_FS *fs)
  174. {
  175.     int i,reclaimed,limit;
  176.  
  177.     reclaimed = 0;
  178.     limit = fs->clusters > MSDOS_FAT12 ? 0xfff7 : 0xff7;
  179.     for (i = 2; i < fs->clusters+2; i++)
  180.     if (!get_owner(fs,i) && fs->fat[i].value && fs->fat[i].value != limit) {
  181.         set_fat(fs,i,0);
  182.         reclaimed++;
  183.     }
  184.     if (reclaimed)
  185.     printf("Reclaimed %d unused cluster%s (%d bytes).\n",reclaimed,
  186.       reclaimed == 1 ?  "" : "s",reclaimed*fs->cluster_size);
  187. }
  188.  
  189.  
  190. static void tag_free(DOS_FS *fs,DOS_FILE *ptr)
  191. {
  192.     DOS_FILE *owner;
  193.     int i,walk,prev;
  194.  
  195.     for (i = 2; i < fs->clusters+2; i++)
  196.     if (fs->fat[i].value && fs->fat[i].value != (fs->clusters > MSDOS_FAT12
  197.       ? 0xfff7 : 0xff7) && !get_owner(fs,i) && !fs->fat[i].prev) {
  198.         prev = 0;
  199.         for (walk = i; walk > 0; walk = next_cluster(fs,walk)) {
  200.         if (!(owner = get_owner(fs,walk))) set_owner(fs,walk,ptr);
  201.         else if (owner != ptr)
  202.                 die("Internal error: free chain collides with file");
  203.             else {
  204.             set_fat(fs,prev,-1);
  205.             break;
  206.             }
  207.         prev = walk;
  208.         }
  209.     }
  210. }
  211.  
  212.  
  213. void reclaim_file(DOS_FS *fs)
  214. {
  215.     DIR_ENT *root;
  216.     DOS_FILE dummy;
  217.     int i,reclaimed,files,next,changed,scan,walk;
  218.     int curr_num,next_free,limit;
  219.  
  220.     root = alloc(fs->root_entries*sizeof(DIR_ENT));
  221.     fs_read(fs->root_start,fs->root_entries*sizeof(DIR_ENT),root);
  222.     limit = fs->clusters > MSDOS_FAT12 ? 0xfff7 : 0xff7;
  223.     for (i = 2; i < fs->clusters+2; i++) fs->fat[i].prev = 0;
  224.     for (i = 2; i < fs->clusters+2; i++) {
  225.     next = fs->fat[i].value;
  226.     if (!get_owner(fs,i) && next && next < fs->clusters+2)
  227.         if (get_owner(fs,next) || !fs->fat[next].value || fs->fat[next].
  228.           value == limit) set_fat(fs,i,-1);
  229.         else fs->fat[next].prev++;
  230.     }
  231.     do {
  232.     tag_free(fs,&dummy);
  233.     changed = 0;
  234.     for (i = 2; i < fs->clusters+2; i++)
  235.         if (fs->fat[i].value && fs->fat[i].value != limit && !get_owner(fs,
  236.           i)) {
  237.         if (!fs->fat[fs->fat[i].value].prev--)
  238.             die("Internal error: prev going below zero");
  239.         set_fat(fs,i,-1);
  240.         changed = 1;
  241.         printf("Broke cycle at cluster %d in free chain.\n",i);
  242.         break;
  243.         }
  244.     }
  245.     while (changed);
  246.     files = reclaimed = curr_num = next_free = 0;
  247.     for (i = 2; i < fs->clusters+2; i++)
  248.     if (get_owner(fs,i) == &dummy && !fs->fat[i].prev) {
  249.         files++;
  250.         while (next_free < fs->root_entries)
  251.         if (IS_FREE(root[next_free].name)) break;
  252.         else next_free++;
  253.         if (next_free == fs->root_entries)
  254.         die("Root directory is full.");
  255.         memset(&root[next_free],0,sizeof(DIR_ENT));
  256.         while (1) {
  257.         sprintf(root[next_free].name,"FSCK%04dREC",curr_num);
  258.         for (scan = 0; scan < fs->root_entries; scan++)
  259.             if (scan != next_free && !strncmp(root[scan].name,
  260.               root[next_free].name,MSDOS_NAME)) break;
  261.         if (scan == fs->root_entries) break;
  262.         if (++curr_num == 10000) die("Unable to create unique name");
  263.         }
  264.         root[next_free].start = CT_LE_W(i);
  265.         for (walk = i; walk > 0; walk = next_cluster(fs,walk)) {
  266.         root[next_free].size = CT_LE_L(CF_LE_L(root[next_free].size)+
  267.           fs->cluster_size);
  268.         reclaimed++;
  269.         }
  270.         fs_write(fs->root_start+next_free*sizeof(DIR_ENT),sizeof(DIR_ENT),
  271.           &root[next_free]);
  272.     }
  273.     free(root);
  274.     if (reclaimed)
  275.     printf("Reclaimed %d unused cluster%s (%d bytes) in %d chain%s.\n",
  276.       reclaimed,reclaimed == 1 ? "" : "s",reclaimed*fs->cluster_size,files,
  277.       files == 1 ? "" : "s");
  278. }
  279.